from heapq import *

class PathNode:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.cost = None
        self.dir = None
        self.px = None
        self.py = None
        self.done = 0
        self.spec = None

class PathManager:

    def __init__(self, blocks=[], forbid=[]):
        self.cache_cost = None
        self.blocks = blocks
        self.forbid = forbid
    """
    This will create a path from coordinate [xs, ys] to [xf, yf] in tiles
    forbid is a list of tile context's that the path may not go through
    The exception is the start and end, which does not have context restriction
    func is a function to call on every node in the path found
    the vars passed into the func will be (tiles, x, y, ['first'|'last'])
    """
    def clear_cache(self):
        self.cache_cost = None

    def find_path(self, level, src, dst, **args):

        args.setdefault("diag",1)
        args.setdefault("bias",0)
        args.setdefault("dpen",0)

        #diag, if 1, can path diagonally, else only nsew
        diag = args['diag']
        #add a penalty for changing directions so that paths are mostly straight lines
        bias = args['bias']
        #add penalty for a diagonal move so nsew moves are preferred
        dpen = args['dpen']

        if self.cache_cost is not None:
            if self.cache_cost[src[0]][src[1]].cost is not None:
                return self.get_path(src, dst)
            
        self.cache_cost = []
        width, height = len(level.tiles), len(level.tiles[0])

        for i in xrange(width):
            self.cache_cost.append([PathNode(i, j) for j in xrange(height)])

        cc = self.cache_cost
        cn = cc[src[0]][src[1]]
        cn.cost = 0

        pq = []
        heappush(pq, (0, cn))
        found = 0

        while not found:
            try:
                min, cn = heappop(pq)
            except IndexError:
                return None
            cn.done = 1
            
            if cn.x == dst[0] and cn.y == dst[1]:
                found = 1
            else:
                for i in xrange(-1,2):
                    for j in xrange(-1,2):
                        #make sure the direction is not 0,0, and that diagonals only
                        #calculated if diag is true
                        if not (i == j == 0) and (diag or abs(i + j) == 1):
                            #print i, j
                            nx, ny = cn.x + i, cn.y + j
                            #check that the new tile pos is within valid bounds
                            if nx >= 0 and nx < width and ny >= 0 and ny < height:
                                pt = level.tiles[cn.x][cn.y]
                                nt = level.tiles[nx][ny]
                                nn = cc[nx][ny]
                                #check that it is not already done, not finished, and not forbidden terrain
                                if not nn.done and ((nn.x == dst[0] and nn.y == dst[1]) or (nt.terrain.name not in self.forbid)):
                                    #check that it is not moving into or out of a diagonally blocked tile
                                    if not (abs(i + j) != 1 and (nt.is_diag_blocked() or pt.is_diag_blocked())):
                                        block_check = sum([nt.is_blocked(bc) for bc in self.blocks])
                                        if block_check == 0:
                                            ncost = min + int(nt.terrain.move_penalty)
                                            if cn.dir != "{0},{1}".format(i, j):
                                                ncost += bias
                                            if abs(i + j) != 1:
                                                ncost += dpen
                                            if nn.cost is None or ncost < nn.cost:
                                                nn.cost = ncost
                                                nn.px, nn.py = cn.x, cn.y
                                                nn.dir = "{0},{1}".format(i, j)
                                                #print ncost, nn.px, nn.py
                                                heappush(pq, (ncost, nn))

        return self.get_path(src, dst)


    def get_path(self, src, dst):
        p = []
        cn = self.cache_cost[dst[0]][dst[1]]
        i = 0
        while cn.px is not None:
            p.append((i, cn))
            i+=1
            cn = self.cache_cost[cn.px][cn.py]
        p.append(('last', cn))

        return p
    